import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * Created by L.jp
 * Description:实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

 * User: 86189
 * Date: 2022-11-14
 * Time: 19:34
 */
class Node {
    int val;
    Node next;
    Node random;
    
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Solution {
    //哈希表法，哈希表存储源节点和赋值的节点，这样减少了搜索时间，复制时直接用哈希表获取源节点的next指针和随机指针
    //时间空间复杂度都是O(n)
    /*public Node copyRandomList(Node head) {
        Map<Node,Node> map=new HashMap<>();
        //把原节点和赋值的节点存放在哈希表
        for(Node cur=head;cur!=null;cur = cur.next){
            map.put( cur,new Node(cur.val));
        }
        //构造和原链表一样的链表，利用哈希表的get方法得到每一个新链表的节点，
        // 构造next节点和random节点其实早就在哈希表中存好了
        for(Node cur=head;cur!=null;cur=cur.next){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
        }
        return map.get(head);
    }*/
    
    
    //方法二：原地修改，不借助哈希表，就是先把原链表的每一个节点后面拼接一个一样的节点作为拷贝的节点
    //然后搞定拷贝节点的random节点
    //最后赋值一个新的头结点给新链表的第一个节点，然后把原链表和复制的链表分割开来，返回新的头结点即可
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        //在源节点后构造一个和原值一样的新节点，然后连接好前后的节点，解决了next指向
        for(Node cur=head,copyNode=null; cur != null; cur = cur.next.next){
            copyNode=new Node( cur.val);
            copyNode.next=cur.next;
            cur.next=copyNode;
        }
        //搞定新节点的random指向
        for(Node cur=head;cur!=null;cur=cur.next.next){  //cur.next.next才会跳到源链表的节点
            if(cur.random!=null){
                //当前cur节点是源节点，cur.next就是值一样的拷贝节点，
                // 拷贝节点的random节点就是当前节点的random节点的下一个节点，这个节点正好和random节点的值一样
                cur.next.random=cur.random.next;
            }
        }
        //分离原链表和新链表
        //先给定新链表的头结点
        Node newHead = head.next;
        //tmp作为cur的后继节点
        for(Node cur=head,tmp=null;cur!=null && cur.next!=null;){
            //保存后继节点
            tmp=cur.next;
            //改变节点指向，断开原节点与拷贝节点的连接
            cur.next=tmp.next;
            //跳到后继节点
            cur=tmp;
        }
        return newHead;
    }
}